The present invention relates to a local relaxation (LR) method for optical flow estimation, and, more particularly, to an LR method for optical flow estimation through a velocity combination term using the Poisson equation (decoupling).
Recently, application of the local relaxation (LR) method for optical flow estimation has shown a much better performance than the Gauss-Seidel relaxation method. However, the direct application of the LR method results in relatively slow convergence, because the Poisson equations in which an optical flow estimation problem is framed are coupled.
Local relaxation (LR) algorithms perform well for estimating optical flow, which is the apparent velocity field of the brightness patterns in successive image frames. An LR algorithm can be applied even with the new regularization method, using a multiscale approach which is not sensitive to the regularization parameter. The LR algorithm is a kind of successive over-relaxation scheme (SOR) with spatially varying relaxation parameters, which outperforms Gauss-Seidel relaxation (GS) when used for optical flow estimation. However, a direct application of the LR algorithm for optical flow estimation may degrade performance. This is because two velocity components of the optical flow field are intrinsically coupled to give a set of coupled Poisson equations. Decoupling of these Poisson equations will make it clear how each decoupled component of velocity can be represented in terms of Jacobi relaxation to help select a better local relaxation factor.
The LR algorithm can be applied to the optical flow if this problem is formulated as a boundary value problem. This formulation starts from the brightness constraint equation which comes from the assumption that local brightness patterns are not changed during the time interval of successive image frames, as shown in the following formula (1); EQU l(x+.delta.x, y+.delta.y, t+.delta.t)=l(x, y, t) (1),
which means that an intensive pattern around an image point (x, y) is moved by the amount of (.delta.x, .delta.y) over a time interval .delta.t without changing its pattern. Expanding the right hand side of formula (1) and ignoring higher order terms, the following formula (2) can be obtained. EQU l(x+.delta.x, y+.delta.y, t+.delta.t)=l(x, y, t)+.delta.x l.sub.x +.delta.x l.sub.y +.delta.x l.sub.t ( 2),
where l.sub.x, l.sub.y and l.sub.t respectively represent horizontal, vertical and temporal gradients of an intensity pattern at position (x, y) at time t.
Combining formulas (1) and (2), and dividing by .delta.t, the following linear relation between gradients and velocity is introduced. EQU l.sub.x u+l.sub.y v+l.sub.t =0 (3),
where u and v are horizontal velocity ##EQU1## and vertical velocity ##EQU2## respectively.
The linear formula (3) is used to measure a local velocity vector. The set of this brightness constraint equation is, however, highly ill-posed for usual image sequences because of the well-known aperture problem. To overcome this short-coming, Horn and Schunck introduced a smoothness constraint which results in the following optimization equation (4); ##EQU3##
The second term of the above equation (4) penalizes the deviation from the smoothness of velocity field and the constant .alpha..sup.2 is for a compromise between both constraints.
The following coupled Poisson equations result directly from the optimization equation (4); ##EQU4## where .alpha. indicates a constant. Each of the coupled Poisson equations can be solved using the iterative methods for inverse problems of a large linear system such as Jacobi relaxation (JR), Gauss-Seidel relaxation (GS), Successive-over relaxation (SOR). Since the equations (5) have spatially varying coefficients due to spatial gradients in the right-hand terms thereof, it is difficult to determine the optimal relaxation parameter in SOR. In this case, LR can be applied to solve the equations iteratively.
The equations (5) might be decoupled using a unitary transform before applying LR to obtain better performance, given the fact that one of the resultant equations has constant relaxation coefficients. This method might show a similar performance to that without decoupling, because the coupling terms of equations (5) are very small when the optimal smoothness constant .alpha. is very large. The constant .alpha. is usually large since, the deviation of the true motion field from the motion constraint is larger than that from the smoothness constraint. But, if the displace frame difference is used to reduce the motion constraint error, the desired optimal smoothness constraint will be so small that the effect of decoupling cannot be negligible.
A local relaxation method will be described as follows. Horizontal (vertical) forward-shift and backward-shift operators, E.sub.x and E.sub.x.sup.-1 (E.sub.y and E.sub.y.sup.-1) are defined as: EQU E.sub.x u(x,y)=u(x+h,y) E.sub.x.sup.-1 u(x,y)=u(x-h,y) (6) EQU E.sub.y u(x,y)=u(x,y+h) E.sub.y.sup.-1 u(x,y)=u(x,y-h),
where h is the discrimination distance.
And, the superposed shift operator E is defined as; EQU E=1/4(E.sub.x +E.sub.x.sup.-1 +E.sub.y +E.sub.y.sup.-1) (7)
The gradients normalized by the smoothness constant to simplify the equations are represented as; ##EQU5##
Then, using the composite shift operator E and the normalized gradients, equations (5) can be represented as; EQU Eu=(1+r.sub.x.sup.2)u+r.sub.x r.sub.y v+r.sub.x r.sub.t EQU Ev=r.sub.y r.sub.x u+(1+r.sub.y.sup.2)v+r.sub.y r.sub.t ( 9)
If the coupling term in each equation, for example, r.sub.x r.sub.y v in the equation for the "u" field, is ignored, the following Jacobi relaxation can be obtained to solve equation (9). ##EQU6##
In this case, the Jacobi operator of each component, i.e., J.sub.u and J.sub.v, can be expressed as follows; ##EQU7## and their local spectral radii are, ##EQU8## where if the image size is M.times.N, P.sub.E is, ##EQU9##
Here, the horizontal motion field "u" will converge faster than the vertical motion field when horizontal gradients are larger than vertical gradients and vice versa. As the spectral radius of the Jacobi operator varies spatially according to spatial gradients, LR can be used to obtain the following equation (14), ##EQU10## where the local relaxation parameters are given by ##EQU11##
As described above, the direct application of LR to equation (9) degrades the convergence speed because equation (9) is coupled.